package leetcode_900;

/**
 *@author 周杨
 *New21Game_837 数学游戏
 *describe:用动态规划 AC 95%
 *2018年10月31日 下午1:37:54
 */
public class New21Game_837 {
	public double new21Game(int N, int K, int W) {
		//可能得到N或者更少的概率
		//当得到K或者更多停止
		//每次获得1-W
		double[] dp = new double[N + W + 1];//可能的最大上线是N+W+1
        for (int k = K; k <= N; ++k)
            dp[k] = 1.0;//初始化
        double S = Math.min(N - K + 1, W);
        for (int k = K - 1; k >= 0; --k) {//每次更新K个区间
            dp[k] = S / W;
            S += dp[k] - dp[k + W];
        }
        return dp[0];
    }
}
